//给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。 
//
// 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序
//列。 
// 
//
// 示例 1： 
//
// 
//输入：nums = [10,9,2,5,3,7,101,18]
//输出：4
//解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
// 
//
// 示例 2： 
//
// 
//输入：nums = [0,1,0,3,2,3]
//输出：4
// 
//
// 示例 3： 
//
// 
//输入：nums = [7,7,7,7,7,7,7]
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 2500 
// -104 <= nums[i] <= 104 
// 
//
// 
//
// 进阶： 
//
// 
// 你可以设计时间复杂度为 O(n2) 的解决方案吗？ 
// 你能将算法的时间复杂度降低到 O(n log(n)) 吗? 
// 
// Related Topics 数组 二分查找 动态规划 
// 👍 2060 👎 0

package com.cute.leetcode.editor.cn;

import org.omg.CORBA.MARSHAL;

import java.util.Arrays;

public class LongestIncreasingSubsequence {
    public static void main(String[] args) {
        int[] nums = {1,3,6,7,9,4,10,5,6};
        new LongestIncreasingSubsequence().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 找出最长递增子序列的长度
         * dp[i]保存的是以nums[i]结尾的最长子序列长度
         * 每次到一个新位置i时都要去查i之前的所有nums[j]<nums[i]的dp，取最大的dp[j] + 1
         */
        public int lengthOfLIS(int[] nums) {
            int len = nums.length;
            int[] dp = new int[len];
            Arrays.fill(dp, 1);//先将所有的元素dp赋值为1，因为长度最少就是1
            int res = 1;
            dp[0] = 1;
            //时间复杂度是n^2
            for (int i = 1; i < len; i++) {
                for (int j = 0; j < i; j++) {
                    if (nums[j]<nums[i]){
                        dp[i] = Math.max(dp[j]+1,dp[i]);
                    }
                }
                res = Math.max(res, dp[i]);
            }
            return res;
        }
        /**
         * 这里的状态转移方程存放的不再是长度，tail[i]存放的是使子串递增长度为i+1的最小末尾数
         * 比如[10, 9, 2, 5, 3, 7, 101, 18]
         * tail[0] = 2 tail[1] = 3 tail[2] = 5依次类推
         * 遍历nums时，如果nums[i]严格大于tail的最后一个元素，就将nums[i]直接添加进去就行
         * 否则需要遍历tail：
         *      如果tail中找到了第一个>nums[i]的数，那么就让其变小
         *      如果tail中找到与nums[i]，则不进行任何操作
         *      而且tail数组是严格单调递增的，所以查找的时候可以使用二分法
         * 需要一个end指针指向tail的尾部
         * tail中的元素在选择时是用到了贪心的思想，所以可以保证tail单调递增
         */
        public int sol2LengthOfLIS(int[] nums){
            int len = nums.length;
            if (len == 1) return len;
            int[] tail = new int[len];
            tail[0] = nums[0];
            int end = 0;
            for (int i = 1; i < len; i++) {
                if (nums[i]>tail[end]){
                    tail[++end] = nums[i];
                }else {//这里是寻找第一个比nums[i]大的位置，由于tail单调递增所以可以二分查找
                    int left = 0;
                    int right = end;
                    int mid;
                    while (left < right){
                        mid = left + (right-left)/2;//向下取整（mid向左取）
                        if (tail[mid]<nums[i]){
                            left = mid +1;
                        }else right = mid;
                    }
                    //这里能保证left的位置绝对是第一个>=nums[i]的位置
                    tail[left] = nums[i];
                }
            }
            return ++end;
        }
        //二刷的时候用的普通的dp，后看题解后使用的tail数组，使用二分查找后时间飞快
    }
//leetcode submit region end(Prohibit modification and deletion)

}















































